package main.剑指OfferⅡ;

import java.util.*;

public class Day17_Day20 {
    public static void main(String[] args) {
        System.out.println("**************************Day17**************************");
        System.out.println("剑指OfferⅡ050.向下的路径节点之和");
        System.out.println("剑指OfferⅡ051.节点之和最大的路径");
        System.out.println("剑指OfferⅡ052.展平二叉搜索树");
        System.out.println("**************************Day18**************************");
        System.out.println("剑指OfferⅡ053.二叉搜索树中的中序后继");
        System.out.println("剑指OfferⅡ054.所有大于等于节点的值之和");
        System.out.println("剑指OfferⅡ055.二叉搜索树迭代器");
        System.out.println("**************************Day19**************************");
        System.out.println("剑指OfferⅡ056.二叉搜索树中两个节点之和");
        System.out.println("剑指OfferⅡ057.值和下标之差都在给定的范围内");
        System.out.println("剑指OfferⅡ058.日程表");
        System.out.println("**************************Day20**************************");
        System.out.println("剑指OfferⅡ059.数据流的第 K 大数值");
        System.out.println("剑指OfferⅡ060.出现频率最高的 k 个数字");
        System.out.println("剑指OfferⅡ061.和最小的 k 个数对");
    }
}

class Offer50{
    HashMap<Long, Integer> prefix;
    public int pathSum(TreeNode root, int targetSum) {
        prefix = new HashMap<>();
        prefix.put(0L, 1);
        return dfs(root, 0, targetSum);
    }

    public int dfs(TreeNode root, long curr, int targetSum) {
        if (root == null) return 0;
        int ret = 0;
        curr += root.val;
        ret = prefix.getOrDefault(curr - targetSum, 0);
        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
        ret += dfs(root.left, curr, targetSum);
        ret += dfs(root.right, curr, targetSum);
        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);
        return ret;
    }
}

class Offer51{
    int maxSum = Integer.MIN_VALUE;
    public int process(TreeNode root){
        if (root == null) return 0;
        int left = process(root.left);
        int right = process(root.right);
        maxSum = Math.max(maxSum, left + root.val + right);//过根节点的可能最大值
        int pathSum = root.val + Math.max(Math.max(0, left), right);//不过根节点或不过子树的可能最大值
        return pathSum < 0 ? 0 : pathSum;
    }
    public int maxPathSum(TreeNode root) {
        process(root);
        return maxSum;
    }
}

class Offer52{
    public TreeNode increasingBST(TreeNode root) {
        Stack<TreeNode> stack=new Stack<>();
        List<Integer> list=new ArrayList<>();
        while (root!=null||!stack.isEmpty()){
            if (root!=null){
                stack.push(root);
                root=root.left;
            }else {
                root=stack.pop();
                list.add(root.val);
                root=root.right;
            }
        }
        TreeNode vir=new TreeNode(-1),curNode=vir;
        for (int val:list){
            curNode.right=new TreeNode(val);
            curNode=curNode.right;
        }
        return vir.right;
    }
}

class Offer53{
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode result=null;
        Stack<TreeNode> stack=new Stack<>();
        List<TreeNode> list=new ArrayList<>();
        while (root!=null||!stack.isEmpty()){
            if (root!=null){
                stack.push(root);
                root=root.left;
            }else {
                root=stack.pop();
                list.add(root);
                root=root.right;
            }
        }
        int i=0;
        for (;i<list.size();i++){
            TreeNode curNode=list.get(i);
            if (curNode==p) break;
        }
        if (i<list.size()-1) result=list.get(i+1);
        return result;
    }
}

class Offer54{
    public void process(TreeNode root,List<Integer> list,List<Integer> preSum){
        if (root==null) return;
        int index=list.indexOf(root.val),totalSum= preSum.get(preSum.size()-1);
        if (index!=list.size()-1){
            root.val=totalSum-preSum.get(index)+ root.val;
        }
        process(root.left,list,preSum);
        process(root.right,list,preSum);
    }
    public TreeNode convertBST(TreeNode root) {
        TreeNode temp=root;
        List<Integer> list=new ArrayList<>(),preSum=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        while (temp!=null|| !stack.isEmpty()){
            if (temp!=null){
                stack.push(temp);
                temp=temp.left;
            }else {
                temp=stack.pop();
                list.add(temp.val);
                temp=temp.right;
            }
        }
        int sum=0;
        for (int i=0;i<list.size();i++){
            preSum.add(sum+list.get(i));
            sum+=list.get(i);
        }
        process(root,list,preSum);
        return root;
    }
}

class Offer55{
    int index;
    List<Integer> list;
    public Offer55(TreeNode root) {
        index=0;
        list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        while (root!=null||!stack.isEmpty()){
            if (root!=null){
                stack.push(root);
                root=root.left;
            }else {
                root=stack.pop();
                list.add(root.val);
                root=root.right;
            }
        }
    }

    public int next() {
        return list.get(index++);
    }

    public boolean hasNext() {
        return index<list.size();
    }
}

class Offer56{
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        while (root!=null||!stack.isEmpty()){
            if (root!=null){
                stack.push(root);
                root=root.left;
            }else {
                root=stack.pop();
                list.add(root.val);
                root=root.right;
            }
        }
        int left=0,right=list.size()-1;
        while (left<right){
            if (list.get(left)+list.get(right)==k) return true;
            else if (list.get(left)+list.get(right)<k) left++;
            else right--;
        }
        return false;
    }
}

class Offer57{
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        TreeSet<Long> set = new TreeSet<Long>();
        for (int i = 0; i < n; i++) {
            Long ceiling = set.ceiling((long) nums[i] - (long) t);
            if (ceiling != null && ceiling <= (long) nums[i] + (long) t) {
                return true;
            }
            set.add((long) nums[i]);
            if (i >= k) {
                set.remove((long) nums[i - k]);
            }
        }
        return false;
    }
}

class Offer58{
    List<Integer> startList,endList;
    public Offer58() {
        startList=new ArrayList<>();
        endList=new ArrayList<>();
    }

    public boolean book(int start, int end) {
        if (startList.isEmpty()) {
            startList.add(start);
            endList.add(end);
            return true;
        }else {
            int lastStart=-1,lastEnd=-1,index=-1,i=0;
            for (i=0;i<startList.size();i++){
                int curStart=startList.get(i),curEnd=endList.get(i);//当前
                if (end<=curStart&&start>=lastEnd){//满足插入
                    index=i;
                    break;
                }
                lastEnd=curEnd;
                lastStart=curStart;
            }
            if (index==-1&&lastEnd<=start) index=startList.size();//判断插入末位
            if (index==-1) return false;
            else {
                startList.add(index,start);
                endList.add(index,end);
                return true;
            }
        }
    }
}

class Offer59{
    PriorityQueue<Integer> queue;
    int k;
    public Offer59(int k, int[] nums) {
        queue = new PriorityQueue<>();
        this.k = k;
        for(int num : nums){
            queue.add(num);
        }
        while(queue.size() > k){
            queue.poll();
        }
    }

    public int add(int val) {
        queue.add(val);
        if(queue.size() > k){
            queue.poll();
        }
        return queue.peek();
    }
}

class Offer60{
    public int[] topKFrequent(int[] nums, int k) {
        int[] result=new int[k];
        Map<Integer,Integer> map=new HashMap<>();
        for (int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        int[][] count=new int[map.size()][2];
        int i=0;
        for (Integer key: map.keySet()){
            count[i][0]=key;
            count[i][1]=map.get(key);
            i++;
        }
        PriorityQueue<int[]> bigHeap=new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1]-o1[1];
            }
        });
        for (int[] c:count) bigHeap.add(c);
        for (int j=0;j<k;j++) result[j]=bigHeap.poll()[0];
        return result;
    }
}

class Offer61{
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> list=new ArrayList<>();
        PriorityQueue<int[]> bigHeap=new PriorityQueue<>(((o1, o2) -> (o1[0]+o1[1])-(o2[0]+o2[1])));
        for (int i=0;i<nums1.length;i++){
            for (int j=0;j< nums2.length;j++){
                int[] temp={nums1[i],nums2[j]};
                bigHeap.offer(temp);
            }
        }
        for (int i=0;i<k&&bigHeap.size()>0;i++) {
            List<Integer> temp=new ArrayList<>();
            int[] cur= bigHeap.poll();
            temp.add(cur[0]);
            temp.add(cur[1]);
            list.add(temp);
        }
        return list;
    }
}